// deque standard header -*-c++-*-
// Copyright 2003-2010 IAR Systems AB. 
#ifndef _DEQUE_
#define _DEQUE_

#ifndef _SYSTEM_BUILD
#pragma system_include
#endif

#include <memory>
#include <stdexcept>
_STD_BEGIN

// IAR memory handling notes.
// Template copying functions (deque, assign, insert) have been implemented 
//   without _Iter_cat, input_iterator_tag usage.
// _Alval should not be used, use _Alval() instead.
// Some _Ty parameters needs to be exchanged for _ParamTy instead. 

#pragma language = save
#pragma language = extended

// DEQUE PARAMETERS
template<class _Ty>
struct _Deque_Constants
{
  enum _Constants
  {       // deque parameters
    _DEQUEMAPSIZ = 8,       /* minimum map size, at least 1 */
    _DEQUESIZ = sizeof (_Ty) <= 1 ? 16
    : sizeof (_Ty) <= 2 ? 8
    : sizeof (_Ty) <= 4 ? 4
    : sizeof (_Ty) <= 8 ? 2 : 1
  };   // elements per block
};

template<class _Ty, class _Ax = allocator<_Ty> >
class __memory_of(_Ty) deque;

// TEMPLATE CLASS _Deque_const_iterator
template<class _Ty,
         class _Alloc>
class _Deque_const_iterator
  : public _Ranit<_Ty, 
                  typename _Alloc::difference_type,
                  typename _Alloc::const_pointer, 
                  typename _Alloc::const_reference>
{       // iterator for nonmutable deque
public:
  typedef _Deque_const_iterator<_Ty, _Alloc> _Myt;
  typedef deque<_Ty, _Alloc> _Mydeque;

  typedef random_access_iterator_tag iterator_category;
  typedef _Ty value_type;
  typedef typename _Alloc::difference_type difference_type;
  typedef typename _Alloc::const_pointer pointer;
  typedef typename _Alloc::const_reference reference;

  typedef typename _Alloc::size_type size_type;

  _Deque_const_iterator()
  {       // construct with null deque pointer
    this->_Mycont = 0;
    _Myoff = 0;
  }

  _Deque_const_iterator(const _Myt& _Right)
    : _Mycont(_Right._Mycont), _Myoff(_Right._Myoff)
  {       // construct with copy of _Right
  }

  _Deque_const_iterator(size_type _Off, const _Mydeque *_Pdeque)
  {       // construct with offset _Off in *_Pdeque
    this->_Mycont = _Pdeque;
    _Myoff = _Off;
  }

  reference operator*() const
  {     // return designated object
    size_type _Block = _Myoff / _Deque_Constants<_Ty>::_DEQUESIZ;
    size_type _Off = _Myoff & (_Deque_Constants<_Ty>::_DEQUESIZ - 1);  // assume power of 2
    if (this->_Mycont->_Mapsize <= _Block)
      _Block -= this->_Mycont->_Mapsize;
    return ((this->_Mycont->_Map)[_Block][_Off]);
  }

  pointer operator->() const
  {       // return pointer to class object
    return (&**this);
  }

  _Myt& operator++()
  {       // preincrement
    ++_Myoff;
    return (*this);
  }

  _Myt operator++(int)
  {       // postincrement
    _Myt _Tmp = *this;
    ++*this;
    return (_Tmp);
  }

  _Myt& operator--()
  {       // predecrement
    --_Myoff;
    return (*this);
  }

  _Myt operator--(int)
  {       // postdecrement
    _Myt _Tmp = *this;
    --*this;
    return (_Tmp);
  }

  _Myt& operator+=(difference_type _Off)
  {       // increment by integer
    _Myoff += _Off;
    return (*this);
  }

  _Myt operator+(difference_type _Off) const
  {       // return this + integer
    _Myt _Tmp = *this;
    return (_Tmp += _Off);
  }

  _Myt& operator-=(difference_type _Off)
  {       // decrement by integer
    return (*this += -_Off);
  }
  
  _Myt operator-(difference_type _Off) const
  {       // return this - integer
    _Myt _Tmp = *this;
    return (_Tmp -= _Off);
  }

  difference_type operator-(const _Myt& _Right) const
  {       // return difference of iterators
    return (_Right._Myoff <= _Myoff 
              ? _Myoff - _Right._Myoff
              : -(difference_type)(_Right._Myoff - _Myoff));
  }

  reference operator[](difference_type _Off) const
  {       // subscript
    return (*(*this + _Off));
  }

  bool operator==(const _Myt& _Right) const
  {       // test for iterator equality
    return (   this->_Mycont == _Right._Mycont
            && _Myoff == _Right._Myoff);
  }

  bool operator!=(const _Myt& _Right) const
  {       // test for iterator inequality
    return (!(*this == _Right));
  }

  bool operator<(const _Myt& _Right) const
  {       // test if this < _Right
    return (this->_Mycont == _Right._Mycont
            && _Myoff < _Right._Myoff);
  }
  
  bool operator>(const _Myt& _Right) const
  {       // test if this > _Right
    return (_Right < *this);
  }
  
  bool operator<=(const _Myt& _Right) const
  {       // test if this <= _Right
    return (!(_Right < *this));
  }
  
  bool operator>=(const _Myt& _Right) const
  {       // test if this >= _Right
    return (!(*this < _Right));
  }
  
  const _Mydeque *_Mycont;        // pointer to deque
  size_type _Myoff;               // offset of element in deque
};

template<class _Ty,
         class _Alloc> inline
_Deque_const_iterator<_Ty, _Alloc> operator+(
  typename _Deque_const_iterator<_Ty, _Alloc>::difference_type _Off,
  _Deque_const_iterator<_Ty, _Alloc> _Next)
{       // add offset to iterator
  return (_Next += _Off);
}

// TEMPLATE CLASS _Deque_iterator
template<class _Ty,
         class _Alloc>
class _Deque_iterator
  : public _Deque_const_iterator<_Ty, _Alloc>
{       // iterator for mutable deque
public:
  typedef _Deque_iterator<_Ty, _Alloc> _Myt;
  typedef _Deque_const_iterator<_Ty, _Alloc> _Mybase;
  typedef deque<_Ty, _Alloc> _Mydeque;
  
  typedef random_access_iterator_tag iterator_category;
  typedef _Ty value_type;
  typedef typename _Alloc::difference_type difference_type;
  typedef typename _Alloc::pointer pointer;
  typedef typename _Alloc::reference reference;

  typedef typename _Alloc::size_type size_type;

  _Deque_iterator()
  {       // construct with null vector pointer
  }

  _Deque_iterator(size_type _Off, const _Mydeque *_Pdeque)
    : _Mybase(_Off, _Pdeque)
  {       // construct with offset _Off in *_Pdeque
  }

  reference operator*() const
  {       // return designated object
    return ((reference)**(_Mybase *)this);
  }

  pointer operator->() const
  {       // return pointer to class object
    return (&**this);
  }

  _Myt& operator++()
  {       // preincrement
    ++*(_Mybase *)this;
    return (*this);
  }
  
  _Myt operator++(int)
  {       // postincrement
    _Myt _Tmp = *this;
    ++*this;
    return (_Tmp);
  }

  _Myt& operator--()
  {       // predecrement
    --*(_Mybase *)this;
    return (*this);
  }

  _Myt operator--(int)
  {       // postdecrement
    _Myt _Tmp = *this;
    --*this;
    return (_Tmp);
  }

  _Myt& operator+=(difference_type _Off)
  {       // increment by integer
    this->_Myoff += _Off;
    return (*this);
  }

  _Myt operator+(difference_type _Off) const
  {       // return this + integer
    _Myt _Tmp = *this;
    return (_Tmp += _Off);
  }

  _Myt& operator-=(difference_type _Off)
  {       // decrement by integer
    return (*this += -_Off);
  }

  _Myt operator-(difference_type _Off) const
  {       // return this - integer
    _Myt _Tmp = *this;
    return (_Tmp -= _Off);
  }

  difference_type operator-(const _Mybase& _Right) const
  {       // return difference of iterators
    return (*(_Mybase *)this - _Right);
  }

  reference operator[](difference_type _Off) const
  {       // subscript
    return (*(*this + _Off));
  }
};

template<class _Ty,
         class _Alloc> inline
_Deque_iterator<_Ty, _Alloc> operator+(
  typename _Deque_iterator<_Ty, _Alloc>::difference_type _Off,
  _Deque_iterator<_Ty, _Alloc> _Next)
{       // add offset to iterator
  return (_Next += _Off);
}



// TEMPLATE CLASS deque
template<class _Ty, class _Ax>
class __memory_of(_Ty) deque
  : _ClassUtil::_AllocHolder<typename _Ax::template rebind<_Ty>::other,
                             !_ClassUtil::_IsZeroSize<_Ax>::_Result>
{       // circular queue of pointers to blocks
public:
#pragma important_typedef        // To ensure enum constants in debug info
  typedef _Deque_Constants<_Ty> _Constants1;

  typedef deque<_Ty, _Ax> _Myt;
  typedef typename _Ax::template rebind<_Ty>::other _Alloc;
  typedef _ClassUtil::_AllocHolder<_Alloc, !_ClassUtil::_IsZeroSize<_Ax>::_Result>
          _Mybase;
  typedef _Alloc allocator_type;
  typedef typename _Alloc::size_type size_type;
  typedef typename _Alloc::difference_type _Dift;
  typedef _Dift difference_type;
  typedef typename _Alloc::pointer _Tptr;
  typedef typename _Alloc::const_pointer _Ctptr;
  typedef _Tptr pointer;
  typedef _Ctptr const_pointer;
  typedef typename _TypeUtil::_CopyMemory<_Ty, _Tptr>::_Type _Tptrm;
  typedef _POINTER_X(_Tptrm, _Alloc) _Mapptr;
  typedef typename _Alloc::reference _Reft;
  typedef _Reft reference;
  typedef typename _Alloc::const_reference const_reference;
  typedef typename _Alloc::value_type value_type;
  typedef typename _TypeUtil::_ParameterType<_Ty>::_Type _ParamTy;

  typedef _Deque_iterator<_Ty, _Alloc> iterator;
  typedef _Deque_const_iterator<_Ty, _Alloc> const_iterator;

//  friend class _Deque_iterator<_Ty, _Alloc>;
  friend class _Deque_const_iterator<_Ty, _Alloc>;

  typedef _STD reverse_iterator<iterator> reverse_iterator;
  typedef _STD reverse_iterator<const_iterator> const_reverse_iterator;

  deque()
    : _Mybase(), _Map(0),
      _Mapsize(0), _Myoff(0), _Mysize(0)
  {       // construct empty deque
  }

  explicit deque(const _Alloc& _Al)
    : _Mybase(_Al), _Map(0),
      _Mapsize(0), _Myoff(0), _Mysize(0)
  {       // construct empty deque with allocator
  }

  explicit deque(size_type _Count)
    : _Mybase(), _Map(0),
      _Mapsize(0), _Myoff(0), _Mysize(0)
  {       // construct from _Count * _Ty()
    _Construct_n(_Count, typename _ClassUtil::_TmpHolder<_Ty>::_Type());
  }

  deque(size_type _Count, _ParamTy _Val)
    : _Mybase(), _Map(0),
      _Mapsize(0), _Myoff(0), _Mysize(0)
  {       // construct from _Count * _Val
    _Construct_n(_Count, _Val); 
  }

  deque(size_type _Count, _ParamTy _Val, const _Alloc& _Al)
    : _Mybase(_Al), _Map(0),
      _Mapsize(0), _Myoff(0), _Mysize(0)
  {       // construct from _Count * _Val with allocator
    _Construct_n(_Count, _Val);
  }

  deque(const _Myt& _Right)
    : _Mybase(_Right._Alval()), _Map(0),
      _Mapsize(0), _Myoff(0), _Mysize(0)
  {       // construct by copying _Right
    _TRY_BEGIN
    insert(begin(), _Right.begin(), _Right.end());
    _CATCH_ALL
    _Tidy();
    _RERAISE;
    _CATCH_END
  }

  template<class _It>
  deque(_It _First,
         _ALLOW_ONLY_ITERATORS(_It, _It) _Last)
    : _Mybase(), _Map(0),
      _Mapsize(0), _Myoff(0), _Mysize(0)
  {       // construct from [_First, _Last)
    _Construct(_First, _Last);
  }

  template<class _It>
  deque(_It _First,
        _ALLOW_ONLY_ITERATORS(_It, _It)  _Last,
        const _Alloc& _Al)
    : _Mybase(_Al), _Map(0),
      _Mapsize(0), _Myoff(0), _Mysize(0)
  {       // construct from [_First, _Last) with allocator
    _Construct(_First, _Last);
  }

  template<class _It>
  void _Construct(_It _First, _It _Last)
  {       // initialize from [_First, _Last), input iterators
    _TRY_BEGIN
    insert(begin(), _First, _Last);
    _CATCH_ALL
    _Tidy();
    _RERAISE;
    _CATCH_END
  }

  void _Construct_n(size_type _Count, _ParamTy _Val)
  {       // construct from _Count * _Val
    _TRY_BEGIN
    _Insert_n(begin(), _Count, _Val);
    _CATCH_ALL
    _Tidy();
    _RERAISE;
    _CATCH_END
  }

  ~deque()
  {       // destroy the deque
    _Tidy();
  }

  _Myt& operator=(const _Myt& _Right)
  {       // assign _Right
    if (this == &_Right)
      ;
    else if (_Right._Mysize == 0)
      clear();
    else if (_Right._Mysize <= _Mysize)
    {       // new sequence not longer, assign elements and erase unused
      iterator _Mid = _STD copy(_Right.begin(), _Right.end(), begin());
      erase(_Mid, end());
    }
    else
    {       // new sequence longer, assign elements and append rest
      const_iterator _Mid = _Right.begin() + _Mysize;
      _STD copy(_Right.begin(), _Mid, begin());
      insert(end(), _Mid, _Right.end());
    }
    return (*this);
  }

  iterator begin()
  {       // return iterator for beginning of mutable sequence
    return (iterator(_Myoff, this));
  }

  const_iterator begin() const
  {       // return iterator for beginning of nonmutable sequence
    return (const_iterator(_Myoff, this));
  }

  iterator end()
  {       // return iterator for end of mutable sequence
    return (iterator(_Myoff + _Mysize, this));
  }

  const_iterator end() const
  {       // return iterator for end of nonmutable sequence
    return (const_iterator(_Myoff + _Mysize, this));
  }

  iterator _Make_iter(const_iterator _Where) const
  {       // make iterator from const_iterator
    return (iterator(_Where._Myoff, this));
  }

  reverse_iterator rbegin()
  {       // return iterator for beginning of reversed mutable sequence
    return (reverse_iterator(end()));
  }

  const_reverse_iterator rbegin() const
  {       // return iterator for beginning of reversed nonmutable sequence
    return (const_reverse_iterator(end()));
  }

  reverse_iterator rend()
  {       // return iterator for end of reversed mutable sequence
    return (reverse_iterator(begin()));
  }

  const_reverse_iterator rend() const
  {       // return iterator for end of reversed nonmutable sequence
    return (const_reverse_iterator(begin()));
  }

  void resize(size_type _Newsize)
  {       // determine new length, padding with _Ty() elements as needed
    resize(_Newsize, typename _ClassUtil::_TmpHolder<_Ty>::_Type());
  }

  void resize(size_type _Newsize, _ParamTy _Val)
  {       // determine new length, padding with _Val elements as needed
    if (_Mysize < _Newsize)
      _Insert_n(end(), _Newsize - _Mysize, _Val);
    else if (_Newsize < _Mysize)
      erase(begin() + _Newsize, end());
  }

  size_type size() const
  {       // return length of sequence
    return (_Mysize);
  }

  size_type max_size() const
  {       // return maximum possible length of sequence
    return (this->_Alval().max_size());
  }

  bool empty() const
  {       // test if sequence is empty
    return (_Mysize == 0);
  }

  allocator_type get_allocator() const
  {       // return allocator object for values
    return (this->_Alval());
  }

  const_reference at(size_type _Pos) const
  {       // subscript nonmutable sequence with checking
    if (_Mysize <= _Pos)
      _Xran();
    return (*(begin() + _Pos));
  }

  reference at(size_type _Pos)
  {       // subscript mutable sequence with checking
    if (_Mysize <= _Pos)
      _Xran();
    return (*(begin() + _Pos));
  }

  const_reference operator[](size_type _Pos) const
  {       // subscript nonmutable sequence
    return (*(begin() + _Pos));
  }

  reference operator[](size_type _Pos)
  {       // subscript mutable sequence
    return (*(begin() + _Pos));
  }

  reference front()
  {       // return first element of mutable sequence
    return (*begin());
  }

  const_reference front() const
  {       // return first element of nonmutable sequence
    return (*begin());
  }

  reference back()
  {       // return last element of mutable sequence
    return (*(end() - 1));
  }

  const_reference back() const
  {       // return last element of nonmutable sequence
    return (*(end() - 1));
  }

  void push_front(_ParamTy _Val)
  {       // insert element at beginning
    if (   _Myoff % _Deque_Constants<_Ty>::_DEQUESIZ == 0
        && _Mapsize <= (_Mysize + _Deque_Constants<_Ty>::_DEQUESIZ) /
                        _Deque_Constants<_Ty>::_DEQUESIZ)
      _Growmap(1);
    size_type _Newoff = _Myoff != 0 ? _Myoff
                                    : _Mapsize * _Deque_Constants<_Ty>::_DEQUESIZ;
    size_type _Block = --_Newoff / _Deque_Constants<_Ty>::_DEQUESIZ;
    if (_Map[_Block] == 0)
      _Map[_Block] = this->_Alval().allocate(_Deque_Constants<_Ty>::_DEQUESIZ);
    this->_Alval().construct(_Map[_Block] + _Newoff %
                             _Deque_Constants<_Ty>::_DEQUESIZ, _Val);
    _Myoff = _Newoff;
    ++_Mysize;
  }

  #pragma basic_template_matching
  template<typename _Ty1>
  void push_front(_Ty1 const & _Val)
  {
    typename _ClassUtil::_TmpHolder<_Ty>::_Type _Tmp(_Val);
    _ParamTy _Tmp2 = _Tmp;
    push_front(_Tmp2);
  }

  void pop_front()
  {       // erase element at beginning
    if (!empty())
    {       // something to erase, do it
      size_type _Block = _Myoff / _Deque_Constants<_Ty>::_DEQUESIZ;
      this->_Alval().destroy(_Map[_Block] + _Myoff %
                             _Deque_Constants<_Ty>::_DEQUESIZ);
      if (_Mapsize * _Deque_Constants<_Ty>::_DEQUESIZ <= ++_Myoff)
        _Myoff = 0;
      if (--_Mysize == 0)
        _Myoff = 0; 
    }
  }

  void push_back(_ParamTy _Val)
  {       // insert element at end
    if (   (_Myoff + _Mysize) % _Deque_Constants<_Ty>::_DEQUESIZ == 0
        && _Mapsize <= (_Mysize + _Deque_Constants<_Ty>::_DEQUESIZ) /
                        _Deque_Constants<_Ty>::_DEQUESIZ)
      _Growmap(1);
    size_type _Newoff = _Myoff + _Mysize;
    size_type _Block = _Newoff / _Deque_Constants<_Ty>::_DEQUESIZ;
    if (_Mapsize <= _Block)
      _Block -= _Mapsize;
    if (_Map[_Block] == 0)
      _Map[_Block] = this->_Alval().allocate(_Deque_Constants<_Ty>::_DEQUESIZ);
    this->_Alval().construct(_Map[_Block] + _Newoff %
                             _Deque_Constants<_Ty>::_DEQUESIZ, _Val);
    ++_Mysize;
  }

  #pragma basic_template_matching
  template<typename _Ty1>
  void push_back(_Ty1 const & _Val)
  {
    typename _ClassUtil::_TmpHolder<_Ty>::_Type _Tmp(_Val);
    _ParamTy _Tmp2 = _Tmp;
    push_back(_Tmp2);
  }

  void pop_back()
  {       // erase element at end
    if (!empty())
    {       // something to erase, do it
      size_type _Newoff = _Mysize + _Myoff - 1;
      size_type _Block = _Newoff / _Deque_Constants<_Ty>::_DEQUESIZ;
      if (_Mapsize <= _Block)
        _Block -= _Mapsize;
      this->_Alval().destroy(_Map[_Block] + _Newoff %
                             _Deque_Constants<_Ty>::_DEQUESIZ);
      if (--_Mysize == 0)
        _Myoff = 0;
    }
  }

  template<class _It>
  _ALLOW_ONLY_ITERATORS(_It, void)
  assign(_It _First, _It _Last)
  {       // assign [_First, _Last)
    _Assign(_First, _Last);
  }

  template<class _It>
  void _Assign(_It _First, _It _Last)
  {       // assign [_First, _Last), input iterators
    erase(begin(), end());
    insert(begin(), _First, _Last);
  }

  void assign(size_type _Count, _ParamTy _Val)
  {       // assign _Count * _Val
    _Assign_n(_Count, _Val);
  }

  iterator insert(const_iterator _Where, _ParamTy _Val)
  {       // insert _Val at _Where
    if (_Where == begin())
    {       // insert at front
      push_front(_Val);
      return (begin());
    }
    else if (_Where == end())
    {       // insert at back
      push_back(_Val);
      return (end() - 1);
    }
    else
    {       // insert inside sequence
      iterator _Mid;
      size_type _Off = _Where - begin();
      // in case _Val is in sequence
      typename _ClassUtil::_TmpHolder<_Ty>::_Type _Tmp(_Val);

      if (_Off < _Mysize / 2)
      {       // closer to front, push to front then copy
        push_front(front());
        _Mid = begin() + _Off;
        _STD copy(begin() + 2, _Mid + 1, begin() + 1);
      }
      else
      {       // closer to back, push to back then copy
        push_back(back());
        _Mid = begin() + _Off;
        _STD copy_backward(_Mid, end() - 2, end() - 1);
      }

      *_Mid = _Tmp;   // store inserted value
      return (_Make_iter(_Mid));
    }
  }

  void insert(const_iterator _Where, size_type _Count, _ParamTy _Val)
  {       // insert _Count * _Val at _Where
    _Insert_n(_Where, _Count, _Val);
  }

  template<class _It>
  _ALLOW_ONLY_ITERATORS(_It, void)
  insert(const_iterator _Where, _It _First, _It _Last)
  {       // insert [_First, _Last) at _Where
    _Insert(_Where, _First, _Last); 
  }

  template<class _It>
  void _Insert(const_iterator _Where, _It _First, _It _Last)
  {       // insert [_First, _Last) at _Where, bidirectional iterators
    size_type _Off = _Where - begin();

    size_type _Rem = _Mysize - _Off;
    size_type _Oldsize = _Mysize;

    if (_First == _Last)
      ;
    else if (_Off < _Rem)
    {       // closer to front
      _TRY_BEGIN
      for (; _First != _Last; ++_First)
        push_front(*_First);        // prepend flipped

      _CATCH_ALL
      for (; _Oldsize < _Mysize; )
        pop_front();    // restore old size, at least
      _RERAISE;
      _CATCH_END

      size_type _Num = _Mysize - _Oldsize;

      if (0 < _Off)
      {       // insert not at beginning, flip new stuff into place
        _Reverse(_Num, _Num + _Off);
        _Reverse(0, _Num + _Off);
      }
      else
        _Reverse(0, _Num);      // flip new stuff in place
    }
    else
    {       // closer to back
      _TRY_BEGIN
      for (; _First != _Last; ++_First)
        push_back(*_First); // append

      _CATCH_ALL
      for (; _Oldsize < _Mysize; )
        pop_back();     // restore old size, at least
      _RERAISE;
      _CATCH_END

      if (_Off < _Oldsize)
      {       // insert not at end, flip new stuff into place
        _Reverse(_Off, _Oldsize);
        _Reverse(_Oldsize, _Mysize);
        _Reverse(_Off, _Mysize);
      }
    }
  }

  void _Reverse(size_type _First, size_type _Last)
  {       // reverse a subrange
    for (; _First != _Last && _First != --_Last; ++_First)
    {       // swap distinct _First and _Last
      iterator _Start = begin();
      // IAR memory support
      typename _ClassUtil::_TmpHolder<value_type>::_Type _Temp(_Start[_First]);

      _Start[_First] = _Start[_Last];
      _Start[_Last] = _Temp;
    }
  }

  iterator erase(const_iterator _Where)
  {       // erase element at _Where
    return (erase(_Where, _Where + 1));
  }

  iterator erase(const_iterator _First_arg, 
                 const_iterator _Last_arg)
  {       // erase [_First, _Last)
    iterator _First = _Make_iter(_First_arg);
    iterator _Last = _Make_iter(_Last_arg);

    size_type _Off = _First - begin();
    size_type _Count = _Last - _First;

    if (_Off < (size_type)(end() - _Last))
    {       // closer to front
      _STD copy_backward(begin(), _First, _Last);     // copy over hole
      for (; 0 < _Count; --_Count)
        pop_front();    // pop copied elements
    }
    else
    {       // closer to back
      _STD copy(_Last, end(), _First);        // copy over hole
      for (; 0 < _Count; --_Count)
        pop_back();     // pop copied elements
    }
    return (begin() + _Off); 
  }

  void clear()
  {       // erase all
    _Tidy();
  }

  void swap(_Myt& _Right)
  {       // exchange contents with _Right
    if (this == &_Right)
      ;       // same object, do nothing
    else if (this->_Alval() == _Right._Alval())
    {       // same allocator, swap control information
      _STD swap(_Map, _Right._Map);
      _STD swap(_Mapsize, _Right._Mapsize);
      _STD swap(_Myoff, _Right._Myoff);
      _STD swap(_Mysize, _Right._Mysize); 
    }
    else
    {       // different allocator, do multiple assigns
      typename _ClassUtil::_TmpHolder<_Myt>::_Type _Ts(*this);

      *this = _Right;
      _Right = _Ts; 
    }
  }

protected:
  typedef typename _Alloc::template rebind<_Tptrm>::other
          _AlmapType; // allocator object for maps

  _AlmapType       _Almap()       { return _AlmapType(this->_Alval()); }
  _AlmapType const _Almap() const { return _AlmapType(this->_Alval()); }

  void _Assign_n(size_type _Count, _ParamTy _Val)
  {       // assign _Count * _Val
    // in case _Val is in sequence
    typename _ClassUtil::_TmpHolder<_Ty>::_Type _Tmp(_Val);
    erase(begin(), end());
    _Insert_n(begin(), _Count, _Tmp); 
  }

  void _Insert_n(const_iterator _Where,
                 size_type _Count, _ParamTy _Val)
  {       // insert _Count * _Val at _Where
    iterator _Mid;
    size_type _Num;
    size_type _Off = _Where - begin();
    size_type _Rem = _Mysize - _Off;
    size_type _Oldsize = _Mysize;

    if (_Off < _Rem)
    {   // closer to front
      _TRY_BEGIN
      if (_Off < _Count)
      {       // insert longer than prefix
        for (_Num = _Count - _Off; 0 < _Num; --_Num)
          push_front(_Val);       // push excess values
        for (_Num = _Off; 0 < _Num; --_Num)
          push_front(begin()[_Count - 1]);        // push prefix

        _Mid = begin() + _Count;
        _STD fill(_Mid, _Mid + _Off, _Val);         // fill in rest of values
      }
      else
      {       // insert not longer than prefix
        for (_Num = _Count; 0 < _Num; --_Num)
          push_front(begin()[_Count - 1]);        // push part of prefix
        
        _Mid = begin() + _Count;
        // in case _Val is in sequence
        typename _ClassUtil::_TmpHolder<_Ty>::_Type _Tmp(_Val);
        _STD copy(_Mid + _Count, _Mid + _Off, _Mid); // copy rest of prefix
        _STD fill(begin() + _Off, _Mid + _Off, _Tmp);        // fill in values
      }
      _CATCH_ALL
      for (; _Oldsize < size(); )
        pop_front();    // restore old size, at least
      _RERAISE;
      _CATCH_END
    }
    else 
    {           // closer to back
      _TRY_BEGIN
      if (_Rem < _Count)
      {       // insert longer than suffix
        for (_Num = _Count - _Rem; 0 < _Num; --_Num)
          push_back(_Val);        // push excess values
        for (_Num = 0; _Num < _Rem; ++_Num)
          push_back(begin()[_Off + _Num]);        // push suffix
        
        _Mid = begin() + _Off;
        _STD fill(_Mid, _Mid + _Rem, _Val);         // fill in rest of values
      }
      else
      {       // insert not longer than prefix
        for (_Num = 0; _Num < _Count; ++_Num)
          push_back(begin()[_Off + _Rem - _Count + _Num]); // push part of prefix

        _Mid = begin() + _Off;
        // in case _Val is in sequence
        typename _ClassUtil::_TmpHolder<_Ty>::_Type _Tmp(_Val);
        _STD copy_backward(_Mid, _Mid + _Rem - _Count,
                      _Mid + _Rem);   // copy rest of prefix
        _STD fill(_Mid, _Mid + _Count, _Tmp);        // fill in values
      }
      _CATCH_ALL
      for (; _Oldsize < size(); )
        pop_back();     // restore old size, at least
      _RERAISE;
      _CATCH_END
    }
  }

  void _Xlen() const
  {       // report length error
    _THROW(length_error, "deque<T> too long");
  }

  void _Xran() const
  {       // report range error
    _THROW(out_of_range, "invalid deque<T> subscript");
  }

  void _Growmap(size_type _Count)
  {       // grow map by _Count pointers
    if (max_size() / _Deque_Constants<_Ty>::_DEQUESIZ - _Mapsize < _Count)
      _Xlen();        // result too long

    size_type _Inc = _Mapsize / 2;  // try to grow by 50%
    if (_Inc < _Deque_Constants<_Ty>::_DEQUEMAPSIZ)
      _Inc = _Deque_Constants<_Ty>::_DEQUEMAPSIZ;
    if (_Count < _Inc && _Mapsize <= max_size() /
        _Deque_Constants<_Ty>::_DEQUESIZ - _Inc)
      _Count = _Inc;
    size_type _Myboff = _Myoff / _Deque_Constants<_Ty>::_DEQUESIZ;
    _AlmapType _Alm(this->_Almap());
    _Mapptr _Newmap = _Alm.allocate(_Mapsize + _Count);
    _Mapptr _Myptr = _Newmap + _Myboff;

    _Myptr = _Uninitialized_copy(_Map + _Myboff,
                                 _Map + _Mapsize, 
                                 _Myptr, _Alm);    // copy initial to end
    if (_Myboff <= _Count)
    {       // increment greater than offset of initial block
      _Myptr = _Uninitialized_copy(_Map,
                                   _Map + _Myboff, 
                                   _Myptr, _Alm);  // copy rest of old
      _Uninitialized_fill_n(_Myptr, _Count - _Myboff,
                            (_Tptr)0, _Alm);       // clear suffix of new
      _Uninitialized_fill_n(_Newmap, _Myboff,
                            (_Tptr)0, _Alm);       // clear prefix of new
    }
    else
    {       // increment not greater than offset of initial block
      _Uninitialized_copy(_Map,
                          _Map + _Count, _Myptr, _Alm); // copy more old
      _Myptr = _Uninitialized_copy(_Map + _Count,
                                   _Map + _Myboff, 
                                   _Newmap, _Alm); // copy rest of old
      _Uninitialized_fill_n(_Myptr, _Count,
                            (_Tptr)0, 
                            _Alm);      // clear rest to initial block
    }

    _Destroy_range(_Map + _Myboff, _Map + _Mapsize, _Alm);
    _Alm.deallocate(_Map, _Mapsize);        // free storage for old

    _Map = _Newmap; // point at new
    _Mapsize += _Count;
  }

  void _Tidy()
  {       // free all storage
    while (!empty())
      pop_back();
    for (size_type _Count = _Mapsize; 0 < _Count; )
    {       // free storage for a block and destroy pointer
      if (*(_Map + --_Count) != 0)
        this->_Alval().deallocate(*(_Map + _Count),
                                  _Deque_Constants<_Ty>::_DEQUESIZ);
      this->_Almap().destroy(_Map + _Count); 
    }

    this->_Almap().deallocate(_Map, _Mapsize);        // free storage for map
    _Mapsize = 0;
    _Map = 0;
  }

  _Mapptr _Map;   // pointer to array of pointers to blocks
  size_type _Mapsize;     // size of map array
  size_type _Myoff;       // offset of initial element
  size_type _Mysize;      // current length of sequence

  enum __iar_constants
  {       // deque parameters
    _IAR_DEQUEMAPSIZ = _Deque_Constants<_Ty>::_DEQUEMAPSIZ,
    _IAR_DEQUESIZ    = _Deque_Constants<_Ty>::_DEQUESIZ
  };   // elements per block
#pragma important_typedef        // To ensure enum constants in debug info
  typedef __iar_constants _Constants2;
};
#pragma language = restore

// deque TEMPLATE OPERATORS
template<class _Ty,
         class _Alloc> inline
void swap(deque<_Ty, _Alloc>& _Left, deque<_Ty, _Alloc>& _Right)
{       // swap _Left and _Right deques
  _Left.swap(_Right);
}

template<class _Ty,
         class _Alloc> inline
bool operator==(const deque<_Ty, _Alloc>& _Left,
                const deque<_Ty, _Alloc>& _Right)
{       // test for deque equality
  return (   _Left.size() == _Right.size()
          && equal(_Left.begin(), _Left.end(), _Right.begin()));
}

template<class _Ty,
         class _Alloc> inline
bool operator!=(const deque<_Ty, _Alloc>& _Left,
                const deque<_Ty, _Alloc>& _Right)
{       // test for deque inequality
  return (!(_Left == _Right));
}

template<class _Ty,
         class _Alloc> inline
bool operator<(const deque<_Ty, _Alloc>& _Left,
               const deque<_Ty, _Alloc>& _Right)
{       // test if _Left < _Right for deques
  return (lexicographical_compare(_Left.begin(), _Left.end(),
                                  _Right.begin(), _Right.end()));
}

template<class _Ty,
         class _Alloc> inline
bool operator<=(const deque<_Ty, _Alloc>& _Left,
                const deque<_Ty, _Alloc>& _Right)
{       // test if _Left <= _Right for deques
  return (!(_Right < _Left));
}

template<class _Ty,
         class _Alloc> inline
bool operator>(const deque<_Ty, _Alloc>& _Left,
               const deque<_Ty, _Alloc>& _Right)
{       // test if _Left > _Right for deques
  return (_Right < _Left);
}

template<class _Ty,
         class _Alloc> inline
bool operator>=(const deque<_Ty, _Alloc>& _Left,
                const deque<_Ty, _Alloc>& _Right)
{       // test if _Left >= _Right for deques
  return (!(_Left < _Right));
}

_STD_END
#endif /* _DEQUE_ */

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

/*
 * Copyright (c) 1992-2009 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
 V5.04:0576 */
